package SubjectTree.One;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import Utility.TreeNode;

/**
 * 难度：中等
 * 
 * 102. 二叉树的层序遍历
 * 	给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
 * 
 * 示例：
 * 	二叉树：[3,9,20,null,null,15,7],
 * 	    3
 * 	   / \
 * 	  9  20
 * 	    /  \
 * 	   15   7
 * 	返回其层序遍历结果：
 * 	[
 * 	  [3],
 * 	  [9,20],
 * 	  [15,7]
 * 	]
 *
 * */

public class LevelOrder {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		LevelOrder tlo = new LevelOrder();
		TreeNode root = TreeNode.MkTree("[3,9,20,null,null,15,7]");
		System.out.println(tlo.levelOrder(root));
	}
	//广度优先搜索
	public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> ret = new ArrayList<List<Integer>>();
		if(root==null) {
			return ret;
		}
		
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		//遍历到队列等于空跳出循环
		while(!queue.isEmpty()) {
			List<Integer> level = new ArrayList<Integer>();
			int currentLevelSize=queue.size();
			//遍历次数等于队列数量
			for(int i=0;i<currentLevelSize;i++) {
				TreeNode node = queue.poll();
				level.add(node.val);
				//把左右支点排入队列中
				if(node.left!=null) {
					queue.offer(node.left);
				}
				if(node.right!=null) {
					queue.offer(node.right);
				}
			}
			ret.add(level);
		}
		return ret;
	}
}
